高考申論題
109年
[資訊處理] 資料結構
第 二 題
📖 題組：
一、考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換（Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到n的排列P中，若一對數字 i和 j，1 ≤ i < j ≤ n，P( j) < P(i)，也就是在排列P中較大的數字 j出現在較小的數字 i左邊（前面），我們稱此對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義為排列P中反向的總數量。請回答下列問題：
一、考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換（Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到n的排列P中，若一對數字 i和 j，1 ≤ i < j ≤ n，P( j) < P(i)，也就是在排列P中較大的數字 j出現在較小的數字 i左邊（前面），我們稱此對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義為排列P中反向的總數量。請回答下列問題：
若給定一個數字1到n的排列P，請提出一個線性遞迴（Linear Recursive）的方式來算出排列P的反向數，並提供虛擬碼（Pseudo-code）與時間複雜度分析。（10分）
📝 此題為申論題
思路引導 VIP
看到「線性遞迴（Linear Recursive）」，要明白它指的是函數在執行時，最多只對自己進行一次遞迴呼叫（通常排除了樹狀遞迴的 Divide and Conquer 如 Merge Sort）。解題思路可以從最後一個元素切入：前 n 個元素的總反向數 = 前 n-1 個元素的總反向數 + 第 n 個元素與前面 n-1 個元素產生的反向數。寫出虛擬碼後，由於遞迴深度為 n，且每次需花費 O(n) 時間尋找與第 n 個元素的反向關係，總時間複雜度即可得出。